枚举

定义

枚举算法我们也称之为穷举算法或者线性搜索，这种算法就是在解决问题的时候去使用所有的方式去解决这个问题，会通过推理去考虑事件发生的每一种可能，最后得出结论。

首先分析问题的对象、范围和判断条件，然后逐一列出所有满足条件的解。

枚举算法的流程图如下：

示例

水仙花数

所谓"水仙花数"是指一个三位数，其各位数字立方和等于该本身。例如：153 是一个水仙花数，因为 $153=1^3+5^3+3^3$。

count = 0
for i in range(100,1000):
	count += 1
	a = int(i / 100)
	b = int(i / 10 % 10)
	c = int((i % 10))
	if a ** 3 + b ** 3 + c ** 3 == i:
		print('flower number:',i)
print('enum count:',count)

水仙花数枚举算法

上述代码就是从 100 枚举到 999，依次判断每一个枚举的数字，是否符合水仙花数的判断条件。

线性搜索

线性搜索又称顺序查找，是一种最简单的查找方法，它的基本思想是从第一个记录开始，逐个比较记录的关键字，直到和给定的 K 值相等，则查找成功；若比较结果与文件中 n 个记录的关键字都不等，则查找失败。

示例

简单查找

输入一个字母 target，在一个字母列表 arr 中查找 l 在第几个位置并输出，不在则输出-1。

按照线性查找的思路，只需要从左到右，逐一循环遍历 arr 中的每一个元素，如果有一个元素与 target 相等，则返回其位置，否则返回-1。

def linearSearch(arr, target):
	for i in range(len(arr)):
		if arr[i] == target:
			return i
	return -1
target = input()
arr = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
result = linearSearch(arr, target)
print(result)

总结

之前判断素数这个问题也可以算是一种枚举算法，如果从 2 枚举到 n，就属于比较笨的枚举方法，如果从 2 枚举到 $\sqrt{n}$，则是优化后的更高效的枚举方法。

一般来说，朴素枚举算法就是不考虑优化，直接列出所有的可能性，逐一进行判断。

它的优缺点如下：

	优点	缺点
枚举算法	简单直观	时空效率低

练习

题目	来源	难度
Diamond Collector	http://oj.oldmoon.cn/p/U1516OB1	容易
Milk Pails	http://oj.oldmoon.cn/p/U1516FB1	容易
Blocks	http://oj.oldmoon.cn/p/U2122FB3	容易
Daisy Chains	http://oj.oldmoon.cn/p/U2021DB2	容易
Cow Gymnastics	http://oj.oldmoon.cn/p/U1920DB1	普通
Lifeguards	http://oj.oldmoon.cn/p/U1718JB2	普通
Why Did the Cow Cross the Road II	http://oj.oldmoon.cn/p/U1617FB2	普通
Counting Liars	http://oj.oldmoon.cn/p/U2122OB2	普通
Triangles	http://oj.oldmoon.cn/p/U1920FB1	普通
Hoof, Paper, Scissors	http://oj.oldmoon.cn/p/U1617JB2	普通
Non-Transitive Dice	http://oj.oldmoon.cn/p/U2122JB2	普通
Lonely Photo	http://oj.oldmoon.cn/p/U2122DB1	普通